课程主页：http://www.inference.org.uk/mackay/itprnn/，http://www.inference.org.uk/itprnn_lectures/

课程视频：https://www.bilibili.com/video/BV14b411G7wn?from=search&seid=1786094286746981315，https://www.youtube.com/watch?v=BCiZc0n6COY&list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6

课程书籍：https://book.douban.com/subject/1893050/

这次回顾第五讲，第五讲介绍了符号流码。

备注：笔记参考了中文书籍。

算数码

设信源符号表为$\mathscr H_{X}=\left\{a_{1}, \cdots, a_{I}\right\}$，其中$a_I$表示“传输结束”。假设信源发出序列$x_{1}, x_{2}, \cdots, x_{n}, \cdots$，算数码的编码器和解码器使用条件概率$P\left(x_{n}=a_{i} | x_{1}, \cdots, x_{n-1}\right)$来产生信号。

二进制和区间

利用二分法的思想，可以将二进制数和$[0,1)$区间对应，例子如下：

具体来说，假设二进制数为$b$，那么其对应了如下区间：

例如$01101$对应了

概率和区间

我们也可以将$P(x_1=a_i)$的概率和区间对应：

此外，我们还能将每个区间$a_i$进一步划分为子区间，并用$a_ia_1,\ldots,a_ia_I$表示，其中区间$a_ia_j$的长度为

重复上述过程可以将$[0,1)$分成区间序列，每个区间对应字符串$x_1x_2\ldots x_N$，区间长度等于该字符串的概率。

算数编码的公式

定义下累积概率和上累积概率

那么

更一般的，对于$x_1x_2\ldots x_N$，计算其概率的方式如下：

  • $u:=0.0$
  • $v:=1.0$
  • $p:=v-u$
  • $\text{for }n=1\text{ to }N$：
    • 计算$Q_n,R_n$
    • $v:=u+pR_n(x_n| x_{1}, \cdots, x_{n-1})$
    • $u:=u+p Q_n(x_n| x_{1}, \cdots, x_{n-1})$
    • $p:=v-u$

计算完概率$p$后，找到二进制数$b$，使得$b$对应的区间是包含$p$对应的区间的最小区间。

编码实例

考虑发送$\text{bbba}\square$的编码过程，其中概率分布如下：

编码过程如下图所示：

在观察第一个b时，编码器只能确定开头为$01,10,11$其中之一，这时候需要看第二个符号b，这时候可以确定前两个比特位$10,11$，接着看第三个符号b，这时候可以确定前两个符号位$10$，然后用同样的方法可以确定其他的比特，最后得到的编码为$100111101$。

译码

假定得到编码$100111101$，我们首先计算概率$P(\mathrm{a}), P(\mathrm{b}),P(\square)$，得到其对应的区间，那么可以得出第一个比特为$\text{b}$，此时我们计算$P(\mathrm{a} | \mathrm{b}), P(\mathrm{b} | \mathrm{b}), P(\square | \mathrm{b})$，得到对应的区间，然后以此类推可以解码其他符号。

Lempel-Ziv编码

这种压缩方法使用指向先前出现的相同子串的指针来取代子串。例如考虑字符串$1011010100010 \cdots$，那么可以将其划分为有序的子串字典，$\lambda, 1,0,11,01,010,00,10, \cdots$，其中$\lambda$表示空串，不难看出每个子串$a$比在其之前出现的某个子串多$1$比特，所以可以使用（指针，比特）的方式传输子串，考虑该例子：